Comparing the ejecta velocities at maximum brightness and narrow circumstellar/interstellar Na D absorption line profiles of a sample of 23 Type Ia supernovae (SNe Ia), we determine that the properties of SN Ia progenitor systems and explosions are intimately connected. As demonstrated by Sternberg et al. (2011), half of all SNe Ia with detectable Na D absorption at the host-galaxy redshift in high-resolution spectroscopy have Na D line profiles with significant blueshifted absorption relative to the strongest absorption component, which indicates that a large fraction of SN Ia progenitor systems have strong outflows. In this study, we find that SNe Ia with blueshifted circumstellar/interstellar absorption systematically have higher ejecta velocities and redder colors at maximum brightness relative to the rest of the SN Ia population. This result is robust at a 98.9-99.8% confidence level, providing the first link between the progenitor systems and properties of the explosion. This finding is further evidence that the outflow scenario is the correct interpretation of the blueshifted Na D absorption, adding additional confirmation that some SNe Ia are produced from a single-degenerate progenitor channel. An additional implication is that either SN Ia progenitor systems have highly asymmetric outflows that are also aligned with the SN explosion or SNe Ia come from a variety of progenitor systems where SNe Ia from systems with strong outflows tend to have more kinetic energy per unit mass than those from systems with weak or no outflows.